home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / pascal / posbm.zip / POSBM.ASM < prev    next >
Assembly Source File  |  1989-06-10  |  5KB  |  199 lines
  1. ;Faster string search routine to substitute the POS()
  2. ;function in Turbo Pascal 4 or 5.
  3. ;Based on the Boyer-Moore algorithm.
  4. ;Program Author: Costas Menico (Dr Dobbs, Jul 89)
  5. ;
  6. ;Declare as follows:
  7. ;    {$F+}
  8. ;    {$L SEARCH.OBJ}
  9. ;    FUNCTION posBM(pat,str : STRING) : BYTE; EXTERNAL;
  10. ;Call as follows:
  11. ;    location := posBM(pat, str);
  12. ;
  13. ;Courtesy of Toad Hall
  14. ;v1.1    Toad Hall Tweaks, 11 Jun 89
  15. ; -    Very minor, no functional changes
  16.  
  17. SKIPARRLENGTH    EQU    256    ;length of the skip array
  18.  
  19. ;function work stack
  20. dstk    STRUC
  21. patlen    dw    ?        ;pattern length (also BP base work area)
  22. strlen    dw    ?            ;str length
  23. skiparr    db    SKIPARRLENGTH DUP(?)    ;skip array
  24. pattxt    dd    0            ;pattern address
  25. strtxt    dd    0            ;string text address
  26. dstk    ENDS
  27.  
  28. ;Total stack (caller's plus work stack)
  29. cstk    STRUC
  30. ourdata    db    SIZE dstk DUP(?)    ;work stack size
  31. bpsave    dw    0            ;save BP here
  32. retaddr    dd    0            ;points to return address
  33. straddr    dd    0            ;points to string address
  34. pataddr    dd    0            ;points to pattern address
  35. cstk    ENDS
  36.  
  37. PARAMSIZE    EQU SIZE pataddr + SIZE straddr    ;size ofr parameter list
  38.  
  39. PUBLIC    PosBM                ;function name declaration
  40.  
  41. CODE    SEGMENT PARA PUBLIC 'CODE'
  42.     ASSUME    CS:CODE
  43.  
  44. ;Entry point to POSBM function
  45.  
  46. PosBM    proc    FAR
  47.     push    bp
  48.     sub    sp,SIZE dstk        ;create work area
  49.     mov    bp,sp
  50.  
  51.     push    DS            ;save caller's DS
  52.     xor    ah,ah
  53.     cld
  54.  
  55. ;Get and save pattern length and address
  56.     lds    si,[bp.pataddr]
  57.     mov    word ptr [bp.pattxt][2],DS
  58.     lodsb                ;get pattern length (1 byte)
  59.     or    al,al            ;if length is null
  60.     jnz    NotNullP
  61.     jmp    NoMatch            ; then exit
  62.  
  63. NotNullP:
  64.     mov    cx,ax            ;save length to check if 1 later
  65.  
  66.     mov    [bp.patlen],ax        ;save pattern length
  67.     mov    word ptr [bp.pattxt],si    ;save address
  68.  
  69. ;Get and save string text length and address
  70.     lds    si,[bp.straddr]
  71.     mov    word ptr [bp.strtxt][2],DS
  72.     lodsb                ;get string length
  73.     or    al,al            ;if string text is null
  74.     jnz    NotNullS
  75.     jmp    NoMatch            ; then exit
  76.  
  77. NotNullS:
  78.     mov    [bp.strlen],ax        ;save string length
  79.     mov    word ptr [bp.strtxt],si    ;save address
  80.  
  81.     cmp    cx,1            ;is pattern length 1 char?
  82.     jne    Do_Boyer_Moore        ;nope
  83.  
  84.     lds    si,[bp.pattxt]        ;yes, do a straight search
  85.     mov    cx,ax            ;still has string length    v1.1
  86.     lodsb                ;get the single char pattern
  87.     les    di,[bp.strtxt]        ;get string address
  88. ;v1.1    mov    cx,[bp.strlen]        ;get string length
  89.     repne    scasb            ;search
  90.     jz    Match1            ;found - adjust last DI psn
  91.      jmp    NoMatch            ;not found, exit
  92.  
  93. Match1:
  94.     mov    si,di
  95.     sub    si,2            ;adjust SI psn
  96.     jmp    ExactMatch
  97.  
  98. Do_Boyer_Moore:
  99.  
  100. ;Fill the ASCII character skiparray with the pattern length
  101.     lea    di,[bp.skiparr]        ;get skip array address
  102.     mov    dx,SS
  103.     mov    ES,dx
  104.     mov    al,byte ptr [bp.patlen]    ;get pattern size
  105.     mov    ah,al            ;put in AH also
  106.     mov    cx,SKIPARRLENGTH / 2    ;array size
  107.     rep    stosw            ;fill with pattern length
  108.  
  109. ;Replace in the ASCII skiparray the corresponding
  110. ;character offset from the end of the pattern minus 1
  111.  
  112.     lds    si,[bp.pattxt]        ;get pattern address
  113.  
  114. ;v1.1 donno why he did this .. he never uses it!
  115. ;v1.1    lea    bx,[bp.skiparr]        ;get skip array address
  116.  
  117. ;v1.1    mov    cx,[bp.patlen]        ;get pattern length
  118.     xor    ah,ah            ;clear MSB            v1.1
  119.     mov    cx,ax            ;AX is still pattern length    v1.1
  120.     dec    cx            ; minus 1
  121.     mov    bx,bp            ;save BP
  122.     lea    bp,[bp.skiparr]        ;get skip array address
  123. ;v1.1    xor    ah,ah
  124. Fill_SkipArray:
  125.     lodsb                ;get char from pattern
  126.     mov    di,ax            ;use it as an index
  127.     mov    [bp+di],cl        ;store the last skip value
  128.     loop    Fill_SkipArray
  129.  
  130.     lodsb
  131.     mov    di,ax
  132.     mov    [bp+di],cl        ;store the last skip value
  133.     mov    bp,bx            ;restore BP
  134.  
  135. ;Now initialize our pattern and string text pointers
  136. ;to start searching
  137.     lds    si,[bp.strtxt]        ;string address
  138.     lea    di,[bp.skiparr]        ;skip array address
  139.     mov    dx,[bp.strlen]        ;string length
  140.     dec    dx            ; minus 1 for each check
  141.     mov    ax,[bp.patlen]        ;pattern length
  142.     dec    ax            ; starting skip value
  143.     xor    bh,bh            ;clear MSB
  144.     std                ;reverse compare
  145.  
  146. ;Get char from text.  Use the char as an index
  147. ;into the skip array, looking for a skip value of 0.
  148. ;If found, execute a brute force search on the pattern.
  149. SearchLast:
  150.     sub    dx,ax            ;check if string exhausted
  151.     jc    NoMatch            ;yes, no match
  152.  
  153.     add    si,ax            ;no - slide pattern with skip value
  154.     mov    bl,[si]            ;get char, use as an index
  155.     mov    al,SS:[di+bx]        ; and get the new skip value
  156.     or    al,al            ;if 0, then possible match
  157.     jne    SearchLast        ; try again by sliding to right
  158.  
  159. ;We have a possible match,
  160. ;therefore do the reverse Brute-force compare
  161.  
  162.     mov    bx,si            ;save string addr
  163.     mov    cx,[bp.patlen]        ;pattern length
  164.     les    di,[bp.pattxt]        ;pattern address
  165.     dec    di            ;adjust
  166.     add    di,cx            ; and add to point to EOS
  167.     repe    cmpsb            ;do reverse compare
  168.     je    ExactMatch        ;if equal, we found a match
  169.  
  170.     mov    ax,1            ;else set skip value to 1
  171.     lea    di,[bp.skiparr]        ;skip array address
  172.     mov    si,bx            ;get string address
  173.     xor    bh,bh            ;No - clear MSB
  174.     jmp    short SearchLast    ;try again
  175.  
  176. ExactMatch:
  177.     mov    ax,si            ;save current psn in string
  178.     lds    si,[bp.strtxt]        ;get start of strtxt
  179.     sub    ax,si            ;sub and add 2 to get psn
  180.     add    ax,2            ; in strtxt where pattern is found
  181.     jmp    short EndSearch        ;exit function
  182.  
  183. NoMatch:
  184.     xor    ax,ax            ;no match, return a 0
  185.  
  186. EndSearch:
  187.     cld
  188.     pop    DS            ;recover
  189.  
  190.     mov    sp,bp            ;recover last stack psn
  191.     add    sp,SIZE dstk        ;clear up work area
  192.     pop    bp            ;recover BP
  193.     ret    PARAMSIZE        ;return with AX the POSBM value
  194.  
  195. PosBM    ENDP
  196.  
  197. CODE    ENDS
  198.     END
  199.